/**
 * \* Created with IntelliJ IDEA.
 * \* User: 冯若航
 * \* Date: 2021/7/11
 * \* Time: 20:12
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class 鸡蛋掉落 {
    public int superEggDrop(int K,int N){
        //memo table
        int[][] middleResults = new int[K + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            // only one egg
            middleResults[1][i] = i;
            // no egg
            middleResults[0][i] = 0;
        }
        for (int i = 1; i <= K; i++) {
            // zero floor
            middleResults[i][0] = 0;
        }

        //start from two eggs
        for(int k=2;k<=K;k++){
            for(int n=1;n<=N;n++){
                int tmp=N*N;
                for(int i=1;i<=n;i++){
                    tmp=Math.min(tmp,Math.max(superEggDrop(k-1,i-1),superEggDrop(k,n-i))+1);
                }
                middleResults[k][n] = tmp;
            }
        }
        return middleResults[K][N];
    }


}